package hot100;


/*
 * Author：江松
 * Date：2023/4/14 11:56
 *
 *
 最佳买卖股票的时机含冷冻期：
 动态规划：
 另f(i,j):划分
 f(i,0)当前持有股票——f(i,0)=max(f(i-1,0),f(i-1,2)-price)，持有之前的或者当前买入
 f(i,1)当前未持有股票，处于冷冻期——说明i-1一定卖出股票，f(i,1)=f(i-1,0)+price
 f(i,2)当前未持有股票，不处于冷冻期——f(i,2)=max(f(i-1,2),f(i-1,1))，上次转移或者上次卖出
 结果就是max(f(n,1),f(n,2))


 空间优化，只与fi-1有关，可以优化为3个常数
 将数组写为常数
 */

public class Main309 {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int f0=-prices[0];
        int f1=0,f2=0;
        for(int i=1;i<n;++i){
            int nf0=Math.max(f0,f2-prices[i]);
            int nf1=f0+prices[i];
            int nf2=Math.max(f2,f1);
            f0=nf0;
            f1=nf1;
            f2=nf2;
        }
        return Math.max(f1,f2);
    }
    /*
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int f[][]=new int[n][3];

        f[0][0]=-prices[0];
        f[0][1]=0;
        f[0][2]=0;
        for(int i=1;i<n;++i){
            f[i][0]=Math.max(f[i-1][0],f[i-1][2]-prices[i]);
            f[i][1]=f[i-1][0]+prices[i];
            f[i][2]=Math.max(f[i-1][2],f[i-1][1]);
        }
        return Math.max(f[n-1][1],f[n-1][2]);
    }
    */
}
